//给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 
//
// 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。 
//
// 
//
// 示例 1： 
//
// 
//输入: s = "leetcode", wordDict = ["leet", "code"]
//输出: true
//解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
// 
//
// 示例 2： 
//
// 
//输入: s = "applepenapple", wordDict = ["apple", "pen"]
//输出: true
//解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
//     注意，你可以重复使用字典中的单词。
// 
//
// 示例 3： 
//
// 
//输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
//输出: false
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 300 
// 1 <= wordDict.length <= 1000 
// 1 <= wordDict[i].length <= 20 
// s 和 wordDict[i] 仅由小写英文字母组成 
// wordDict 中的所有字符串 互不相同 
// 
//
// Related Topics 字典树 记忆化搜索 数组 哈希表 字符串 动态规划 👍 2284 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2023-09-15 09:37:07
 * @description 139.单词拆分
 */
public class WordBreak{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new WordBreak().new Solution();
		solution.wordBreak("leetcode",new ArrayList<>(Arrays.asList("leet","code")));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	/*dfs+记忆化搜索*/
	public boolean wordBreak1(String s, List<String> wordDict) {
		Set<String> set = new HashSet<>();
		for (String word : wordDict) {
			set.add(word);
		}
		// 使用一个数组来记录从每个索引位置开始的子问题是否可解
		Boolean[] memo = new Boolean[s.length()];
		return dfs(s, set, 0, memo);
	}

	private boolean dfs(String s, Set<String> set, int index, Boolean[] memo) {
		if (index >= s.length()) {
			return true;
		}
		if (memo[index] != null) {
			return memo[index];
		}
		StringBuffer tem = new StringBuffer();
		for (int i = index; i < s.length(); i++) {
			tem.append(s.charAt(i));
			//如果字典包含当前的词语，且切割下去可行，则标记true并返回
			if (set.contains(tem.toString()) && dfs(s, set, i + 1, memo)) {
				memo[index] = true;
				return true;
			}
		}
		//标记从当前位置开始切割不行
		memo[index] = false;
		return false;

	}

	/*动态规划*/
	public boolean wordBreak(String s, List<String> wordDict) {
		int [] dp=new int [s.length()+1];
		dp[0]=1;//截取到i，字符串能否被表示
		for (int i = 1; i <= s.length(); i++) {
			for (int j = 0; j < wordDict.size(); j++) {
				String t = wordDict.get(j);
				//当前截取字符串长度 大于等于字典字符串 且 字典字符串在截取字符串末尾
				if(i>=t.length() && s.startsWith(t, i-t.length())){
					dp[i]=Math.max(dp[i-t.length()],dp[i]);
					if(dp[i]==1) break;
				}
			}
		}
		return dp[s.length()]==1;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
